/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/maximum-gap
   @Language: C++
   @Datetime: 19-11-21 17:29
   */

class Solution {
	struct Bucket{
		int minv, maxv;
		bool used;
		Bucket(int n=INT_MAX, int m=INT_MIN, bool u=false):minv(n),maxv(m),used(u){}
	};
public:
	int maximumGap(vector<int>& nums) {
		if(nums.size()<2) return 0;
		const auto min_max=minmax_element(nums.begin(),nums.end());
		const int n=*min_max.first, m=*min_max.second;      // min, max
		const long s=max(1L,(0L+m-n)/((long)nums.size()-1));// bucket size
		vector<Bucket> buckets((0L+m-n)/s+1);
		for(const auto &num:nums){
			const long i=(0L+num-n)/s;
			buckets[i]={min(num,buckets[i].minv),max(num,buckets[i].maxv),true};
		}
		long gap=0, prev_max=n;
		for(const auto &b:buckets){
			if(!b.used) continue;
			gap=max(gap,b.minv-prev_max);
			prev_max=b.maxv;
		}
		return gap;
	}
};
